
//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
// Related Topics 链表 双指针 
// 👍 1322 👎 0

package leetcode.editor.cn;

/**
 * @Author:xpengfei
 * @Date: 2021-04-16 22:29:01
 * @Description：删除链表的倒数第 N 个结点
 */
public class Ques19RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        Solution solution = new Ques19RemoveNthNodeFromEndOfList().new Solution();
    }

    //Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            // 双指针解法 第一个指针与第二个指针之间间隔了 n  个节点，此时第一个指针遍历完成后，第二个指针指向待删除节点的前一个节点
            ListNode cursor = head;
            ListNode secondCursor = head;
            while (cursor != null) {
                if (n < 0) {
                    ListNode tempNode = secondCursor.next;
                    secondCursor = tempNode;
                }
                cursor = cursor.next;
                n--;
            }
            if (n == 0) {
                return head.next;
            }
            secondCursor.next = secondCursor.next == null ? null : secondCursor.next.next;
            return head;
        }

    /*
    // 方法内为第一种解法
    public void method1() {
        ListNode tempNode = head;
        int nodeSum = 0;
        while (tempNode != null) {
            nodeSum++;
            tempNode = tempNode.next;
        }
        int index = nodeSum - n;
        int flag = 1;
        ListNode cursor = head;
        while (cursor != null) {
            if (index == 0) {
                head = cursor.next;
                break;
            }
            if (flag == index) {
                ListNode tempNode1 = cursor.next;
                cursor.next = tempNode1 == null ? null : tempNode1.next;
            }
            flag++;
            cursor = cursor == null ? null : cursor.next;
        }
        return head;
    }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}